/*
* Authors: Savenko Maria
*           * * *
*           * * *
* This file contains implementation of Ramsey algorithm.
*/



#include "stdafx.h"
#include "ramsey_algorithm.h"



ramsey_algorithm::ramsey_algorithm(graph_t & g_) {
    g = g_;
}

//main body of algorithm
bool ramsey_algorithm::clique_removal(){

    if (num_vertices(g) == 0){
        cout << "Graph is empty."<< endl;
        independent_set.clear();
        return false;
    }

    cout << "Ramsey algorithm started..." << endl;

    vertex_list local_i_set;
    clique_list c_blocks;
    pair_list ramsey_result;
    
    while (num_vertices(g) != 0){
        ramsey(g, ramsey_result);
        form_curr_i_set(ramsey_result, local_i_set, c_blocks);
        remove_subgraph(ramsey_result.first);
    }

    independent_set = local_i_set;
    return true;
}


void ramsey_algorithm::form_curr_i_set(pair_list & p_list, vertex_list & i_set, clique_list & c_blocks){
    
    c_blocks.push_back(p_list.first);

    if (i_set.empty() || i_set.size() < p_list.second.size()){
        i_set = p_list.second;
    }
}


bool ramsey_algorithm::ramsey(graph_t & g_, pair_list & p_list){

    if (num_vertices(g_) == 0){
        return false;
    }
    
    vertex_t v = vertex(0,g_);
    graph_t v_neighbours = g_, v_non_neighbours = g_;
    graph_vertex s = {v,g_[v].name};
    divide_into_subgraphs(s, v_neighbours,v_non_neighbours);
    
    pair_list ramsey_result_1;
    ramsey(v_neighbours, ramsey_result_1);
    pair_list ramsey_result_2;
    ramsey(v_non_neighbours, ramsey_result_2);
    
    ramsey_result_1.first.push_back(g_[v].name);
    ramsey_result_2.second.push_back(g_[v].name);
    p_list.first = ramsey_result_1.first.size() > ramsey_result_2.first.size() ? ramsey_result_1.first : ramsey_result_2.first;
    p_list.second = ramsey_result_1.second.size() > ramsey_result_2.second.size() ? ramsey_result_1.second : ramsey_result_2.second;

    return true;
}


//construct graphs with neighbours and non-neighbours of v
void ramsey_algorithm::divide_into_subgraphs(graph_vertex const v, graph_t & neighbours, graph_t & non_neighbours){

    graph_traits<graph_t>::adjacency_iterator i, iend;
    graph_traits<graph_t>::vertex_iterator vi, vi_end;
    list<string> list_2_delete;
    tie(i, iend) = adjacent_vertices(v.v, non_neighbours);

    while ( i != iend ){
        delete_vertex(*i, non_neighbours);
        tie(i, iend) = adjacent_vertices(v.v, non_neighbours);
    }

    tie(vi, vi_end) = vertices(non_neighbours);
    while (vi != vi_end){
        list_2_delete.push_back(non_neighbours[*vi].name);
        ++vi;
    }

    tie(vi, vi_end) = vertices(non_neighbours);
    while (vi != vi_end){
        --vi_end;
        if ( non_neighbours[*vi_end].name == v.name)
            delete_vertex(*vi_end, non_neighbours);
    }

    tie(vi, vi_end) = vertices(neighbours);
    while(vi != vi_end && !list_2_delete.empty()) {
        if (neighbours[*vi].name == list_2_delete.front()){
            delete_vertex(*vi, neighbours);
            list_2_delete.pop_front();
        }
        else
          ++vi;
    }
}


void ramsey_algorithm::remove_subgraph(vertex_list list){

    graph_traits<graph_t>::adjacency_iterator i, iend;
    vertex_t v;

    find_vertex_by_name(list.back(), v);
        

    tie(i, iend) = adjacent_vertices(v, g);

    while ( list.size() > 1 ){
        if (g[*i].name == list.front()){
            delete_vertex(*i, g);
            list.pop_front();
            tie(i, iend) = adjacent_vertices(v, g);
        }
        else ++i;
    }

    delete_vertex(v,g);
}


void ramsey_algorithm::delete_vertex(vertex_t v, graph_t & g_) const{

    clear_vertex(v,g_);
    remove_vertex(v,g_);
}


bool ramsey_algorithm::find_vertex_by_name (std::string const v_name, vertex_t & vertex){
    
    graph_traits<graph_t>::vertex_iterator i, iend;
    tie(i, iend) = vertices(g);

    while(i != iend) {
        if (g[*i].name == v_name){
            vertex = *i;
            return true;
        }
        ++i;
    }

    return false;
}


void ramsey_algorithm::print_independent_set() const{

    cout << "Maximum Independent Set found: " << endl;

	for (vertex_list::const_iterator j = independent_set.begin(); j != independent_set.end(); ++j) {
		cout << *j << " ";
	}
	cin.get();
}